1. Field of the Invention
This application relates generally to wireless data networks, and specifically to an admission control for contention-based access to a wireless communication medium.
2. Background of the Invention
Wireless local area networks (WLAN) are being used for convenient interconnection of portable computers to office data processing networks and to the Internet. Presently there is a desire to increase WLAN data throughput and quality of service in order to support real-time multimedia applications such as voice over Internet Protocol (IP) telephony and video streaming. For example, the Institute of Electrical and Electronics Engineers (IEEE) of Washington, D.C., is promulgating a standard 802.11 n for WLAN to provide a data throughput of at least 100 Mbit/sec.
One way of increasing the WLAN data throughput and quality of service is to use the bandwidth of the wireless transmission medium more efficiently. Because user stations in the WLAN share access to the wireless transmission medium, a considerable amount of the existing bandwidth is unavailable for transmission of user data, and instead is consumed in a process of scheduling access of the traffic flows to the wireless transmission medium. In general, the nature of the wireless transmission medium precludes the user stations from being synchronized to the extent that interference between the user stations is unlikely. Therefore, collision avoidance techniques are used in the process of scheduling access of the traffic flows to the wireless transmission medium.
Efficient methods of scheduling access of the traffic flows to the wireless transmission medium in a WLAN are the subject of IEEE standard 802.11e. Traffic flows can be serviced using either of two medium access methods, depending on the flow's preference. The first access method, called Hybrid Controlled Channel Access (HCCA), is polling based. In this first method, a Hybrid Coordination Function (HCF) grants transmission opportunities (TXOP) to all participating flows based on a schedule. The second access method, called Enhanced Distributed Channel Access (EDCA), is contention-based, in which flows compete to access the channel. In this second method, flows transmit packets whenever they sense that the shared medium is idle for a sufficient period of time. The Hybrid Coordination Function determines when each HCCA flow gets a chance to transmit and when control is ceded to EDCA traffic.
The following references are related to scheduling access to the wireless communication medium of an IEEE 802.11 WLAN:                [1] IEEE 802.11 Standard. Wireless LAN medium access control (MAC) and physical (PHY) layer specifications, IEEE, Washington, D.C., 1999.        [2] Part 11. Wireless medium access control (MAC) and physical (PHY) layer specifications: Medium access control (MAC) quality of service (QoS) enhancements, January 2004.        [3] J. Hui and M. Devetsikiotis, “Desinging improved MAC packet schedulers for 802.11e WLAN,” in Proceedings of IEEE GLOBECOM, 2003.        [4] D. Pong and T. Moors, “Call admission control for IEEE 802.11 contentionaccess mechanism,” in Proceedings of IEEE GLOBECOM, 2003.        [5] G. Bianchi, “Performance analysis of the IEEE 802.11 distributed coordination function,” IEEE Journal on Selected Areas in Comm., vol. 18, no. 3, pp. 535, 547 2000.        [6] O. Tickoo and B. Sikdar, “Queuing analysis and delay mitigation in IEEE 802.11 random access MAC based wireless networks,” in Proceedings of IEEE INFOCOM, 2004.        [7] Leonard Kleinrock, Queuing Systems. Volume 1: Theory, John Wiley & Sons, New York, 1975.        [8] Leonard Kleinrock, Queuing Systems. Volume 2: Computer Applications, John Wiley & Sons, New York, 1976        [9] ITU-T Recommendations, 1996.        
References [3] and [4] study and analyze features of IEEE 802.11e. In [3], the authors provide an improved version of the model in [5] to account for IEEE 802.11e's features, and use their improved model to estimate the saturated throughput. The work in [4] proposes an admission control algorithm for the IEEE 802.11e EDCA based on throughput estimation. The work in [6] presents an analytical model for evaluating the queuing delays at nodes in IEEE 802.11 WLANs. Although this work does consider unsaturated networks, it applies to IEEE 802.11 WLANs.
An IEEE 802.11e quality of service (QoS) facility provides medium access control (MAC) enhancements to support applications with QoS requirements. These QoS enhancements are made available to all QoS stations (QSTAs) associated with a QoS access point (QAP). The hybrid coordination function (HCF) is implemented by all QSTAs.
The IEEE 802.11e EDCA mechanism provides differentiated and distributed access to the wireless channel using eight different user priorities (UPs). To provide support for the delivery of traffic with UPs at the QSTAs, the EDCA mechanism defines four access categories (ACs). QSTAs in each AC use an enhanced DCF (EDCF) to contend for transmission opportunities (TXOPs) all using an identical set of EDCA parameters specified by the QAP.
The EDCA parameters specified by the QAP include an arbitration inter-frame space (AIFS) period, an initial contention window (W0) and/or a maximum contention window (Wm), and a persistent factor f. Before proceeding with transmission, QSTAs with higher UPs are allowed to wait for an arbitration inter-frame space (AIFS) period shorter than those with lower UPs. QSTAs with higher UPs are allowed to have smaller sizes of their initial (W0) and/or maximum (Wm) contention windows. In the following description, Wm=fmW0 where m, referred to as number of backoff stages, will be used to characterize Wm. QSTAs can further be differentiated among each other via using different values of the persistent factor f; i.e., higher priority ACs can use smaller values of f than those with lower priority.
Prior to transmitting a packet, a QSTA must first sense the medium to be idle for the AIFS period. Then, to reduce collision, the QSTA must wait for an additional random backoff period calculated as b×T, where b is a number, called backoff counter, selected from a uniform distribution in the interval [0, W0−1], and T is the length of a time slot period. W0 is a fixed number. While waiting, the QSTA decrements its counter by 1 every idle time slot. Every time the medium becomes busy, the QSTA must freeze its backoff counter. Once the counter is frozen, the QSTA resumes decrementing the counter by 1 every idle time slot after sensing the medium again idle for a AIFS period. When the counter reaches 0, the QSTA proceeds with transmission. In case of unsuccessful transmission, the QSTA keeps retransmitting the packet until it either succeeds or reaches a threshold number of attempts. At the ith retransmission attempt, the contention window size W must equal Wi=max{fi×W0,Wm}. Upon a successful transmission, the contention window is reset to its initial size.
The IEEE 802.11e EDCA mechanism provides a general framework for admission control, but it does not specify precisely when to admit a new flow so as to preserve the QoS of existing flows. The work in [4] attempts to address this problem by estimating the throughput that flows would achieve if a new flow with certain parameters were admitted, by dealing with the EDCA parameters of minimum contention window size and transmission opportunity durations. The objective in [4] is to limit the total admitted traffic in the WLAN below the total achievable throughput, so that the current admitted traffic can be protected and channel utilization will not degrade significantly. A difficulty in implementing this approach in 802.11 lies in estimating the value of the achievable throughput in the WLAN.
The solution proposed in [4] is to estimate the throughput of the flows based on the monitored collision rate of each flow and parameters decided at run-time including the minimum collision window, the maximum collision window, the physical layer transmission rate, and the TXOP duration. From this information, the transmission probability for a flow i at saturation is calculated from the following formula:
                              P          ⁡                      (                                                            tx                  ⁢                                                                          ⁢                  in                  ⁢                                                                          ⁢                  a                  ⁢                                                                          ⁢                  slot                                ❘                flow                            =              i                        )                          =                              2            ⁢                          (                              1                -                                  2                  ⁢                                      p                    i                                                              )                                                                          (                                  1                  -                                      2                    ⁢                                          p                      i                                                                      )                            ⁢                              (                                  W                  +                  1                                )                                      +                                          p                i                            ⁢                              W                ⁡                                  (                                      1                    -                                                                  (                                                  2                          ⁢                                                      p                            i                                                                          )                                            b                                                        )                                                                                        (        1        )                            pi=long term collision probability of flow i        W=CWmin size used for flow i        b=maximum backoff stage with CWmax=(CWmin+1)×2b−1        
The achievable throughput for the flow is then calculated from the transmission probability for the flow using the following equation:
      Achievable    ⁢                  ⁢          throughput      ⁡              [        i        ]              =                                                        P              ⁡                              (                                                                            successful                      ⁢                                                                                          ⁢                      transmission                                        ❘                    flow                                    =                  1                                )                                      ×                                                            Data            ⁢                                                  ⁢            payload            ⁢                                                  ⁢            size                                                                                                  P                ⁡                                  (                  collision                  )                                            ×                              Duration                collision                                      +                                                                                          P                ⁡                                  (                                      slot                    ⁢                                                                                  ⁢                    is                    ⁢                                                                                  ⁢                    idle                                    )                                            ×              aSlotTime                        +                                                                          P              ⁡                              (                                  successful                  ⁢                                                                          ⁢                  transmission                                )                                      ×                          Duration              success                                          
If admitting the new flow causes the achievable throughputs for the flows to be insufficient, then admission of the new flow is rejected. Otherwise, the admission controller searches for the best parameters for CWmin and TXOP duration (if used), given the required bandwidth of the new flow.